//class Solution {
//public:
//    vector<vector<string>> groupAnagrams(vector<string>& strs) {
//        unordered_map<string, vector<string>> hash;
//        for (auto& str : strs)
//        {
//            string tmp = str;
//            sort(tmp.begin(), tmp.end());
//            if (hash.find(tmp) != hash.end())
//                hash[tmp].push_back(str);
//            else
//                hash.insert({ tmp, {str} });
//        }
//
//        vector<vector<string>> ret;
//        for (auto& [a, b] : hash)
//            ret.push_back(b);
//        return ret;
//    }
//};


class AnimalShelf {
public:
    AnimalShelf() {}

    void enqueue(vector<int> animal) {
        if (animal[1]) dogs.push(animal[0]);
        else cats.push(animal[0]);
    }

    vector<int> dequeueAny() {
        if (cats.empty()) return dequeueDog();
        if (dogs.empty()) return dequeueCat();
        if (cats.front() < dogs.front()) return dequeueCat();
        else return dequeueDog();
    }

    vector<int> dequeueDog() {
        if (dogs.empty()) return { -1, -1 };
        int id = dogs.front();
        dogs.pop();
        return { id, 1 };
    }

    vector<int> dequeueCat() {
        if (cats.empty()) return { -1, -1 };
        int id = cats.front();
        cats.pop();
        return { id, 0 };
    }
    queue<int> cats, dogs;
};